from typing import List


class Solution:
    def minTaps(self, n: int, distances: List[int]) -> int:
        ranges = []
        for i, num in enumerate(distances):
            left, right = max(0, i - num), min(n, i + num)
            ranges.append([left, right])
        ranges.sort(key=lambda x: (x[0], -x[1]))

        # 当前区间可到达的坐标、下一个区间可到达的坐标
        ans = 0
        i1, i2 = 0, 0
        for left, right in ranges:
            # 下一个区间也不能到达新区间的左侧边界，中间的间隔无法被灌溉
            if i2 < left:
                return -1

            # 当前区间不能到达新区间的左侧边界，需要将使用下一个区间
            elif i1 < left <= i2:
                ans += 1
                i1, i2 = i2, max(i2, right)

            # 当前区间能够到达新区间的左侧边界，更新下一个区间能够到达的最远坐标
            else:
                i2 = max(i2, right)

        # 需要使用下一个区间
        if i1 < i2:
            ans += 1

        return ans


if __name__ == "__main__":
    print(Solution().minTaps(n=5, distances=[3, 4, 1, 1, 0, 0]))  # 1
    print(Solution().minTaps(n=3, distances=[0, 0, 0, 0]))  # -1
    print(Solution().minTaps(n=7, distances=[1, 2, 1, 0, 2, 1, 0, 1]))  # 3
    print(Solution().minTaps(n=8, distances=[4, 0, 0, 0, 0, 0, 0, 0, 4]))  # 2
    print(Solution().minTaps(n=8, distances=[4, 0, 0, 0, 4, 0, 0, 0, 4]))  # 1
